Waarom is het verwerken van een gesorteerde array sneller dan het verwerken van een ongesorteerde array?

U bent het slachtoffer van mislukte branchevoorspelling.
Wat is branchevoorspelling?
Overweeg een spoorwegknooppunt:
Afbeelding door Mecanismo, via Wikimedia Commons. Gebruikt onder de CC-By-SA 3.0-licentie.
Stel nu, omwille van de discussie, dat dit terug is in de jaren 1800 - vóór lange afstands- of radiocommunicatie.
Je bent de operator van een kruispunt en je hoort een trein aankomen. Je hebt geen idee welke kant het op moet. Je stopt de trein om de chauffeur te vragen welke richting hij wil. En dan stel je de schakelaar op de juiste manier in.
Treinen zijn zwaar en hebben veel traagheid. Het duurt dus een eeuwigheid om op te starten en te vertragen.
Is er een betere manier? U raadt welke richting de trein zal gaan!
Als je het goed hebt geraden, gaat het verder.
Als je het verkeerd hebt geraden, zal de kapitein stoppen, achteruit rijden en tegen je schreeuwen dat je de schakelaar moet omdraaien. Daarna kan het het andere pad opnieuw opstarten.
Als je elke keer goed raadt, hoeft de trein nooit te stoppen. Als je te vaak verkeerd gokt, zal de trein veel tijd besteden aan stoppen, achteruit rijden en opnieuw opstarten.
Beschouw een if-statement: op processorniveau is het een branch-instructie:
Je bent bewerker en je ziet een filiaal. Je hebt geen idee welke kant het op zal gaan. Wat doe jij? U stopt de uitvoering en wacht tot de vorige instructies zijn voltooid. Daarna vervolg je het juiste pad.
Moderne processors zijn ingewikkeld en hebben lange pijplijnen. Het duurt dus een eeuwigheid om "op te warmen" en te "vertragen".
Is er een betere manier? U raadt welke richting de tak zal gaan!
Als je het goed hebt geraden, ga je door met de uitvoering.
Als je het verkeerd hebt geraden, moet je de pijpleiding doorspoelen en terugrollen naar de tak. Vervolgens kunt u het andere pad opnieuw starten.
Als je elke keer goed raadt, hoeft de uitvoering nooit te stoppen. Als u te vaak verkeerd gokt, besteedt u veel tijd aan het stoppen, terugdraaien en opnieuw opstarten.
Dit is branchevoorspelling. Ik geef toe dat het niet de beste analogie is, aangezien de trein de richting gewoon met een vlag kon aangeven. Maar bij computers weet de processor pas op het laatste moment in welke richting een branch zal gaan.
Dus hoe zou u strategisch raden om het aantal keren te minimaliseren dat de trein achteruit moet rijden en het andere pad moet afleggen? Je kijkt naar het verleden! Als de trein 99% van de tijd naar links gaat, gok je naar links. Als het afwisselt, wisselt u uw gissingen af. Als het elke drie keer een kant op gaat, raad je hetzelfde ...
Met andere woorden, je probeert een patroon te identificeren en het te volgen. Dit is min of meer hoe branchevoorspellers werken.
De meeste applicaties hebben brave takken. Dus moderne branchevoorspellers zullen doorgaans> 90% hitpercentages behalen. Maar wanneer u wordt geconfronteerd met onvoorspelbare takken zonder herkenbare patronen, zijn branchevoorspellers vrijwel nutteloos.
Verder lezen: artikel "Branch voorspeller" op Wikipedia.
Zoals hierboven aangegeven, is de boosdoener deze if-statement:
if (data [c]> = 128)
som + = data [c];
Merk op dat de gegevens gelijkmatig zijn verdeeld tussen 0 en 255. Wanneer de gegevens zijn gesorteerd, zal ongeveer de eerste helft van de iteraties niet in het if-statement komen. Daarna voeren ze allemaal het if-statement in.
Dit is erg vriendelijk voor de vertakkingsvoorspeller, aangezien de vertakking meerdere keren achter elkaar dezelfde richting uitgaat. Zelfs een eenvoudige verzadigingsteller zal de tak correct voorspellen, behalve de paar iteraties nadat deze van richting is veranderd.
Snelle visualisatie:
T = tak genomen
N = tak niet bezet
gegevens [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
tak = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (gemakkelijk te voorspellen)
Wanneer de gegevens echter volledig willekeurig zijn, wordt de vertakkingsvoorspeller onbruikbaar gemaakt, omdat deze geen willekeurige gegevens kan voorspellen. Er zal dus waarschijnlijk ongeveer 50% verkeerde voorspelling zijn (niet beter dan willekeurig gissen).
gegevens [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
tak = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (volledig willekeurig - moeilijk te voorspellen)
Dus wat kan er worden gedaan?
Als de compiler de vertakking niet kan optimaliseren tot een voorwaardelijke verplaatsing, kun je enkele hacks proberen als je bereid bent de leesbaarheid op te offeren voor prestaties.
Vervangen:
if (data [c]> = 128)
som + = data [c];
met:
int t = (data [c] - 128) >> 31;
som + = ~ t & data [c];
Dit elimineert de branch en vervangt deze door enkele bitsgewijze bewerkingen.
(Merk op dat deze hack niet strikt gelijk is aan de originele if-statement. Maar in dit geval is hij geldig voor alle invoerwaarden van data [].)
Benchmarks: Core i7 920 @ 3,5 GHz
C ++ - Visual Studio 2010 - x64-versie
// Branch - Willekeurig
seconden = 11,777
// Branch - Gesorteerd
seconden = 2.352
// Branchless - Willekeurig
seconden = 2.564
// Branchless - gesorteerd
seconden = 2.587
Java - NetBeans 7.1.1 JDK 7 - x64
// Branch - Willekeurig
seconden = 10,93293813
// Branch - Gesorteerd
seconden = 5.643797077
// Zonder takken -Willekeurig
seconden = 3.113581453
// Branchless - gesorteerd
seconden = 3.186068823
Observaties:
Met de tak: Er is een enorm verschil tussen de gesorteerde en ongesorteerde gegevens.
Met de hack: er is geen verschil tussen gesorteerde en ongesorteerde gegevens.
In het geval van C ++ is de hack eigenlijk een beetje langzamer dan bij de branch wanneer de gegevens worden gesorteerd.
Een algemene vuistregel is om gegevensafhankelijke vertakking in kritieke lussen (zoals in dit voorbeeld) te vermijden.
Bijwerken:
GCC 4.6.1 met -O3 of -ftree-vectorize op x64 kan een voorwaardelijke zet genereren. Er is dus geen verschil tussen de gesorteerde en ongesorteerde gegevens - beide zijn snel.
(Of enigszins snel: voor het reeds gesorteerde geval kan cmov langzamer zijn, vooral als GCC het op het kritieke pad plaatst in plaats van alleen maar toe te voegen, vooral op Intel vóór Broadwell waar cmov een latentie van 2 cycli heeft: gcc-optimalisatievlag -O3 maakt code langzamer dan -O2)
VC ++ 2010 is niet in staat om voorwaardelijke zetten te genereren voor deze tak, zelfs niet onder / Ox.
Intel C ++ Compiler (ICC) 11 doet iets wonderbaarlijks. Het verwisselt de twee lussen, waardoor de onvoorspelbare tak naar de buitenste lus wordt gehesen. Het is dus niet alleen immuun voor misverstanden, het is ook twee keer zo snel als wat VC ++ en GCC kunnen genereren! Met andere woorden, ICC profiteerde van de testlus om de benchmark te verslaan ...
Als je de Intel-compiler de branchless-code geeft, vectoriseert deze hem gewoon helemaal rechts ... en is hij net zo snel als met de branch (met de lusuitwisseling).
Dit laat zien dat zelfs volwassen moderne compilers enorm kunnen variëren in hun vermogen om code te optimaliseren ...
|
Branch voorspelling.
Met een gesorteerde array zijn de conditiegegevens [c]> = 128 eerst onwaar voor een reeks waarden, en worden ze vervolgens waar voor alle latere waarden. Dat is makkelijk te voorspellen. Met een ongesorteerde array betaalt u voor de vertakkingskosten.
|
De reden waarom de prestaties drastisch verbeteren wanneer de gegevens worden gesorteerd, is dat de vertakkingsboete is verwijderd, zoals prachtig wordt uitgelegd in het antwoord van Mysticial.
Als we nu naar de code kijken
if (data [c]> = 128)
som + = data [c];
we kunnen ontdekken dat de betekenis van deze specifieke if ... else ... branch is om iets toe te voegen wanneer aan een voorwaarde is voldaan. Dit type vertakking kan eenvoudig worden omgezet in een voorwaardelijke verplaatsingsinstructie, die zou worden gecompileerd in een voorwaardelijke verplaatsingsinstructie: cmovl, in een x86-systeem. De vertakking en dus de mogelijke voorspellingsstraf voor de vertakking wordt verwijderd.
In C, dus C ++, is de instructie die direct (zonder enige optimalisatie) zou compileren in de voorwaardelijke verplaatsingsinstructie in x86, de ternaire operator ...? ...: .... Dus herschrijven we de bovenstaande verklaring in een gelijkwaardige:
som + = data [c]> = 128? gegevens [c]: 0;
Met behoud van de leesbaarheid kunnen we de versnellingsfactor controleren.
Op een Intel Core i7-2600K @ 3,4 GHz en Visual Studio 2010 Release Mode is de benchmark (formaat gekopieerd van Mysticial):
x86
// Branch - Willekeurig
seconden = 8.885
// Branch - Gesorteerd
seconden = 1.528
// Branchless - Willekeurig
seconden = 3.716
// Branchless - gesorteerd
seconden = 3,71
x64
// Branch - Willekeurig
seconden = 11.302
// Branch - Gesorteerd
seconden = 1.830
// Branchless - Willekeurig
seconden = 2,736
// Branchless - gesorteerd
seconden = 2,737
Het resultaat is robuust in meerdere tests. We krijgen een grote versnelling als het resultaat van de vertakking onvoorspelbaar is, maar we lijden een beetje als het voorspelbaar is. Bij gebruik van een voorwaardelijke verplaatsing is de prestatie in feite hetzelfde, ongeacht het datapatroon.
Laten we nu eens nader kijken door de x86-assembly die ze genereren te onderzoeken. Voor de eenvoud gebruiken we twee functies max1 en max2.
max1 gebruikt de voorwaardelijke branch if ... else ...:
int max1 (int a, int b) {
als (a> b)
retourneer een;
anders
terug b;
}
max2 gebruikt de ternaire operator ...? ...: ...:
int max2 (int a, int b) {
terug a> b? een: b;
}
Op een x86-64-machine genereert GCC -S de onderstaande assembly.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
vertrekken
ret
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
vertrekken
ret
max2 gebruikt veel minder code vanwege het gebruik van instructie cmovge. Maar de echte winst is dat max2 geen vertakkingssprongen, jmp, omvat, wat een aanzienlijke prestatieverbinding zou hebben als het voorspelde resultaat niet juist is.
Dus waarom presteert een voorwaardelijke zet beter?
In een typische x86-processor is de uitvoering van een instructie onderverdeeld in verschillende fasen. We hebben grofweg verschillende hardware om met verschillende fasen om te gaan. We hoeven dus niet te wachten op een instructie om te eindigen om een ​​nieuwe te starten. Dit heet pipelining.
In een filiaalgeval wordt de volgende instructie bepaald door de voorgaande, dus we kunnen geen pipelining doen. We moeten wachten of voorspellen.
In een geval van voorwaardelijke verplaatsing,de uitvoeringsvoorwaardelijke verplaatsingsinstructie is verdeeld in verschillende fasen, maar de eerdere fasen zoals Fetch en Decode zijn niet afhankelijk van het resultaat van de vorige instructie; alleen de laatste fasen hebben het resultaat nodig. We wachten dus een fractie van de uitvoeringstijd van één instructie. Dit is de reden waarom de voorwaardelijke verplaatsingsversie langzamer is dan de branch wanneer de voorspelling eenvoudig is.
Het boek Computer Systems: A Programmer's Perspective, tweede editie legt dit in detail uit. U kunt Sectie 3.6.6 raadplegen voor instructies voor voorwaardelijk verplaatsen, hoofdstuk 4 voor Processorarchitectuur en Sectie 5.11.2 voor speciale behandeling voor straffen voor filiaalvoorspelling en onjuiste voorspelling.
Soms kunnen sommige moderne compilers onze code optimaliseren voor assemblage met betere prestaties, soms kunnen sommige compilers dat niet (de code in kwestie gebruikt de native compiler van Visual Studio). Als we het prestatieverschil kennen tussen een vertakking en een voorwaardelijke verplaatsing wanneer deze onvoorspelbaar is, kunnen we code schrijven met betere prestaties wanneer het scenario zo complex wordt dat de compiler ze niet automatisch kan optimaliseren.
|
Als u nieuwsgierig bent naar nog meer optimalisaties die aan deze code kunnen worden gedaan, overweeg dan dit:
Beginnend met de originele lus:
voor (unsigned i = 0; i <100000; ++ i)
{
voor (unsigned j = 0; j  = 128)
som + = data [j];
}
}
Met lusuitwisseling kunnen we deze lus veilig wijzigen in:
voor (unsigned j = 0; j  = 128)
som + = data [j];
}
}
Dan kun je zien dat de if voorwaardelijk constant is tijdens de uitvoering van de i-lus, dus je kunt de if eruit hijsen:
voor (unsigned j = 0; j  = 128)
{
voor (unsigned i = 0; i <100000; ++ i)
{
som + = data [j];
}
}
}
Dan zie je dat de binnenste lus kan worden samengevouwen tot één enkele uitdrukking, ervan uitgaande dat het drijvende-kommamodel dit toestaat (/ fp: fast wordt bijvoorbeeld gegooid)
voor (unsigned j = 0; j  = 128)
{
som + = data [j] * 100.000;
}
}
Die is 100.000 keer sneller dan voorheen.
|
Sommigen van ons zouden ongetwijfeld geïnteresseerd zijn in manieren om code te identificeren die problematisch is voor de vertakkingsvoorspeller van de CPU. De Valgrind-tool cachegrind heeft een branch-predictor simulator, mogelijk gemaakt door de --branch-sim = yes vlag te gebruiken. Het doorlopen van de voorbeelden in deze vraag, met het aantal buitenste lussen teruggebracht tot 10000 en gecompileerd met g ++, geeft deze resultaten:
Gesorteerd:
== 32551 == Vestigingen: 656.645.130 (656.609.208 cond + 35.922 ind)
== 32551 == Onjuiste voorspellingen: 169.556 (169.095 cond + 461 ind)
== 32551 == Foutief tarief: 0,0% (0,0% + 1,2%)
Ongesorteerd:
== 32555 == Vestigingen: 655.996.082 (655.960.160 cond + 35.922 ind)
== 32555 == Onjuiste voorspellingen: 164.073.152 (164.072.692 cond + 460 ind)
== 32555 == Verkeerd tarief: 25,0% (25,0% + 1,2%)
Als we naar de regel-voor-regel uitvoer van cg_annotate gaan, zien we voor de betreffende lus:
Gesorteerd:
Bc Bcm Bi Bim
10.001 4 0 0 voor (unsigned i = 0; i <10000; ++ i)
. . . . {
. . . . // primaire lus
327.690.000 10.016 0 0 voor (unsigned c = 0; c  = 128)
0 0 0 0 som + = data [c];
. . . . }
. . . . }
Ongesorteerd:
Bc Bcm Bi Bim
10.001 4 0 0 voor (unsigned i = 0; i <10000; ++ i)
. . . . {
. . . . // primaire lus
327.690.000 10.038 0 0 voor (unsigned c = 0; c  = 128)
0 0 0 0 som + = data [c];
. . . . }
. . . . }
Hiermee kun je gemakkelijk de problematische regel identificeren - in de ongesorteerde versie veroorzaakt de if (data [c]> = 128) regel 164.050.007 verkeerd voorspelde voorwaardelijke vertakkingen (Bcm) onder het vertakkingsvoorspellermodel van cachegrind, terwijl het slechts 10.006 veroorzaakt in de gesorteerde versie .
Als alternatief kunt u onder Linux het subsysteem prestatiemeteritems gebruiken om dezelfde taak uit te voeren, maar met native prestaties met behulp van CPU-tellers.
perf stat ./sumtest_sorted
Gesorteerd:
Prestatiemeterstatistieken voor './sumtest_sorted':
11808.095776 taakklok # 0.998 CPU's gebruikt
1.062 context-schakelaars # 0,090 K / sec
14 CPU-migraties # 0,001 K / sec
337 pagina-fouten # 0,029 K / sec
26.487.882.764 cycli # 2,243 GHz
41.025.654.322 instructies # 1,55 insn per cyclus
6.558.871.379 vestigingen # 555.455 M / sec
567.204 branch-missers # 0,01% van alle branches
11.827228330 seconden verstreken tijd
Ongesorteerd:
Prestatietegenstatistieken voor './sumtest_unsorted':
28877.954344 taakklok # 0.998 CPU's gebruikt
2584 context-schakelaars # 0,089 K / sec
18 CPU-migraties # 0,001 K / sec
335 pagina-fouten # 0,012 K / sec
65.076.127.595 cycli # 2,253 GHz
41.032.528.741 instructies # 0,63 insn per cyclus
6.560.579.013 takken # 227.183 M / sec
1.646.394.749 filiaal-missers # 25,10% van alle filialen
28.935500947 seconden verstreken tijd
Het kan ook broncode-annotatie uitvoeren met demontage.
perf record -e branch-misses ./sumtest_unsorted
perf annoteren -d somtest_unsorted
Procent | Broncode en demontage van sumtest_unsorted
------------------------------------------------
...
: som + = data [c];
0.00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4.60: 400a26: cltq
0.00: 400a28: add% rax, -0x30 (% rbp)
...
Zie de prestatiehandleiding voor meer details.
|
Ik heb zojuist deze vraag en de antwoorden gelezen, en ik voel dat er een antwoord ontbreekt.
Een veelgebruikte manier om branchevoorspelling te elimineren waarvan ik heb vastgesteld dat deze bijzonder goed werkt in beheerde talen, is een tabel opzoeken in plaats van een branch te gebruiken (hoewel ik het in dit geval niet heb getest).
Deze aanpak werkt in het algemeen als:
het is een kleine tabel en wordt waarschijnlijk in de cache opgeslagen in de processor, en
je draait dingen in een vrij krappe lus en / of de processor kan de gegevens vooraf laden.
Achtergrond en waarom
Vanuit processorperspectief is uw geheugen traag. Om het snelheidsverschil te compenseren, zijn er een aantal caches in je processor ingebouwd (L1 / L2 cache). Dus stel je voor dat je mooie berekeningen maakt en bedenk dat je een stukje geheugen nodig hebt. De processor krijgt zijn 'laad'-bewerking en laadt het geheugen in de cache - en gebruikt vervolgens de cache om de rest van de berekeningen uit te voeren. Omdat het geheugen relatief traag is, zal deze 'belasting' uw programma vertragen.
Net als vertakkingsvoorspelling, werd dit geoptimaliseerd in de Pentium-processors: de processor voorspelt dat hij een stukje gegevens moet laden en probeert dat in de cache te laden voordat de bewerking daadwerkelijk de cache raakt. Zoals we al hebben gezien, gaat vertakkingsvoorspelling soms vreselijk mis - in het ergste geval moet je teruggaan en eigenlijk wachten op een geheugenbelasting, die een eeuwigheid zal duren (met andere woorden: falende vertakkingsvoorspelling is slecht, een herinnering laden nadat een vertakkingsvoorspelling mislukt is, is gewoon vreselijk!).
Gelukkig voor ons, als het geheugentoegangspatroon voorspelbaar is, laadt de processor het in zijn snelle cache en is alles in orde.
Het eerste dat we moeten weten, is wat klein is? Hoewel kleiner over het algemeen beter is, is een vuistregel om vast te houden aan opzoektabellen die <= 4096 bytes groot zijn. Als bovengrens: als uw opzoektabel groter is dan 64K is het waarschijnlijk de moeite waard om opnieuw te overwegen.
Een tafel construeren
Dus we hebben ontdekt dat we een kleine tafel kunnen maken. Het volgende dat u moet doen, is een opzoekfunctie installeren. Opzoekfuncties zijn meestal kleine functies die een aantal basisbewerkingen met gehele getallen gebruiken (en, of, xor, verschuiven, optellen, verwijderen en misschien vermenigvuldigen). U wilt uw invoer door de opzoekfunctie laten vertalen naar een soort 'unieke sleutel' in uw tabel, die u vervolgens eenvoudig het antwoord geeft van al het werk dat u wilde dat het deed.
In dit geval:> = 128 betekent dat we de waarde kunnen behouden, <128 betekent dat we er vanaf kunnen komen. De eenvoudigste manier om dat te doen is door een 'AND' te gebruiken: als we het behouden, AND we het met 7FFFFFFF; als we er vanaf willen komen, wij EN het met 0. Merk ook op dat 128 een macht van 2 is - dus we kunnen doorgaan en een tabel maken van 32768/128 gehele getallen en deze vullen met één nul en veel 7FFFFFFFF's.
Beheerde talen
U vraagt ​​zich misschien af ​​waarom dit goed werkt in beheerde talen. Beheerde talen controleren immers de grenzen van de arrays met een vertakking om ervoor te zorgen dat u niet verknoeit ...
Nou, niet echt ... :-)
Er is behoorlijk wat werk verzet om deze branch voor beheerde talen te elimineren. Bijvoorbeeld:
voor (int i = 0; i  = 128)? c: 0;
}
// Test
DateTime startTime = System.DateTime.Now;
lange som = 0;
voor (int i = 0; i <100000; ++ i)
{
// Primaire lus
voor (int j = 0; j  = 128. Dat betekent dat we gemakkelijk een enkele bit kunnen extraheren die ons vertelt of we een waarde willen of niet: door te verschuiven de data aan de rechterkant 7 bits, we houden een 0 bit of een 1 bit over, en we willen de waarde alleen optellen als we een 1 bit hebben. Laten we dit bit het "beslissingsbit" noemen.
Door de 0/1 waarde van de beslissingsbit te gebruiken als een index in een array, kunnen we code maken die even snel is, of de gegevens nu gesorteerd of niet gesorteerd zijn. Onze code voegt altijd een waarde toe, maar als de beslissingsbit 0 is, voegen we de waarde ergens toe waar we niet om geven. Hier is de code:
// Test
clock_t start = klok ();
lang lang a [] = {0, 0};
lange lange som;
voor (unsigned i = 0; i <100000; ++ i)
{
// Primaire lus
voor (unsigned c = 0; c > 7);
a [j] + = data [c];
}
}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
som = a [1];
Deze code verspilt de helft van de toevoegingen, maar heeft nooit een vertakkingsfout. Het is enorm sneller op willekeurige gegevens dan de versie met een feitelijke if-instructie.
Maar bij mijn testen was een expliciete opzoektabel iets sneller dan dit, waarschijnlijk omdat het indexeren in een opzoektabel iets sneller ging dan het verschuiven van bits. Dit laat zien hoe mijn code de opzoektabel instelt en gebruikt (onvoorstelbaar lut genoemd voor "LookUp Table" in de code). Hier is de C ++ -code:
// Declareer en vul de opzoektabel in
int lut [256];
voor (unsigned c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Gebruik de opzoektabel nadat deze is gebouwd
voor (unsigned i = 0; i <100000; ++ i)
{
// Primaire lus
voor (unsigned c = 0; c  waarde)
knooppunt = knooppunt-> pLeft;
anders
knooppunt = knooppunt-> pRight;
deze bibliotheek zou zoiets doen als:
i = (x  waarde);
knooppunt = knooppunt-> link [i];
Hier is een link naar deze code: Red Black Trees, Eternally Confuzzled
|
In het gesorteerde geval kun je het beter doen dan te vertrouwen op succesvolle branchevoorspelling of een andere branchless-vergelijkingstruc: verwijder de branch volledig.
Inderdaad, de array is gepartitioneerd in een aaneengesloten zone met data <128 en een andere met data> = 128. Dus je zou het partitiepunt moeten vinden met een dichotomische zoekopdracht (met Lg (arraySize) = 15 vergelijkingen), en doe dan een rechte accumulatie van dat punt.
Iets als (niet aangevinkt)
int i = 0, j, k = arraySize;
terwijl (i > 1;
if (data [j]> = 128)
k = j;
anders
ik = j;
}
som = 0;
voor (; i > 1;
voor (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
voor (sum = 0; i  = 128)
/ \
/ \
/ \
waar onwaar
/ \
/ \
/ \
/ \
B) som + = data [c]; C) voor loop of print ().
Zonder vertakkingsvoorspelling zou het volgende gebeuren:
Om instructie B of instructie C uit te voeren, zal de processor moeten wachten tot instructie A niet bereikt tot de EX-fase in de pijplijn, aangezien de beslissing om naar instructie B of instructie C te gaan afhangt van het resultaat van instructie A. Dus de pijplijn zal er zo uitzien.
wanneer als voorwaarde true retourneert:
Wanneer als voorwaarde false retourneert:
Als resultaat van het wachten op het resultaat van instructie A, is het totale aantal CPU-cycli dat in het bovenstaande geval is doorgebracht (zonder vertakkingsvoorspelling; voor zowel waar als onwaar) 7.
Dus wat is branchevoorspelling?
De vertakkingsvoorspeller zal proberen te raden welke kant een vertakking (een als-dan-anders-structuur) zal gaan voordat dit zeker bekend is. Het zal niet wachten tot instructie A de EX-fase van de pijplijn bereikt, maar het zal de beslissing raden en naar die instructie gaan (B of C in het geval van ons voorbeeld).
In het geval van een juiste gok, ziet de pijplijn er ongeveer zo uit:
Als later wordt vastgesteld dat de gok niet klopte, worden de gedeeltelijk uitgevoerde instructies verwijderd en begint de pijplijn opnieuw met de juiste vertakking, waardoor er vertraging ontstaat.
De tijd die wordt verspild in het geval van een verkeerde voorspelling van een vertakking, is gelijk aan het aantal fasen in de pijplijn van de ophaalfase tot de uitvoeringsfase. Moderne microprocessors hebben de neiging om vrij lange pijpleidingen te hebben, zodat de vertraging van de verkeerde voorspelling tussen 10 en 20 klokcycli ligt. Hoe langer de pijplijn, hoe groter de behoefte aan een goede vertakkingsvoorspeller.
In de code van het OP, de eerste keer dat de voorwaardelijke, de aftakvoorspeller geen informatie heeft om de voorspelling op te baseren, dus de eerste keer zal hij willekeurig de volgende instructie kiezen. Later in de for-lus kan het de voorspelling baseren op de geschiedenis.
Voor een array die in oplopende volgorde is gesorteerd, zijn er drie mogelijkheden:
Alle elementen zijn minder dan 128
Alle elementen zijn groter dan 128
Sommige beginnende nieuwe elementen zijn minder dan 128 en worden later groter dan 128
Laten we aannemen dat de voorspeller bij de eerste run altijd de ware branch zal aannemen.
Dus in het eerste geval zal het altijd de waarheid zijnbranch omdat historisch gezien al zijn voorspellingen correct zijn.
In het tweede geval zal het aanvankelijk verkeerd voorspellen, maar na een paar iteraties zal het correct voorspellen.
In het derde geval zal het aanvankelijk correct voorspellen totdat de elementen kleiner zijn dan 128. Daarna zal het enige tijd mislukken en het zichzelf corrigeren wanneer het in de geschiedenis een mislukte vertakkingsvoorspelling ziet.
In al deze gevallen zal het aantal fouten te gering zijn en als gevolg daarvan hoeft het slechts een paar keer de gedeeltelijk uitgevoerde instructies te negeren en opnieuw te beginnen met de juiste vertakking, wat resulteert in minder CPU-cycli.
Maar in het geval van een willekeurige ongesorteerde array, zal de voorspelling de gedeeltelijk uitgevoerde instructies moeten negeren en meestal opnieuw moeten beginnen met de juiste branch, wat resulteert in meer CPU-cycli in vergelijking met de gesorteerde array.
|
Een officieel antwoord zou zijn van
Intel - De kosten van misverstanden in de vestigingen vermijden
Intel - Branch and Loop reorganisatie om misverstanden te voorkomen
Wetenschappelijke artikelen - computerarchitectuur voor branchevoorspelling
Boeken: J.L. Hennessy, D.A. Patterson: Computerarchitectuur: een kwantitatieve benadering
Artikelen in wetenschappelijke publicaties: T.Y. Ja, Y.N. Patt deed veel hiervan op branchevoorspellingen.
Je kunt aan dit mooie diagram ook zien waarom de branchevoorspeller in de war raakt.
Elk element in de originele code is een willekeurige waarde
data [c] = std :: rand ()% 256;
dus de voorspeller zal van kant veranderen als de std :: rand () blaast.
Aan de andere kant, als het eenmaal is gesorteerd, zal de voorspeller eerst naar een toestand van sterk niet genomen gaan en wanneer de waarden veranderen naar de hoge waarde, zal de voorspeller in drie runs helemaal veranderen van sterk niet genomen naar sterk genomen.
|
In dezelfde regel (ik denk dat dit door geen enkel antwoord werd benadrukt) is het goed om te vermelden dat je soms (vooral in software waar de prestaties ertoe doen - zoals in de Linux-kernel) enkele if-uitspraken kunt vinden zoals de volgende:
if (waarschijnlijk (alles_is_ok))
{
/* Doe iets */
}
of vergelijkbaar:
if (onwaarschijnlijk (very_improbable_condition))
{
/* Doe iets */
}
Zowel waarschijnlijk () als onwaarschijnlijk () zijn in feite macro's die zijn gedefinieerd door zoiets als de __builtin_expect van de GCC te gebruiken om de compiler te helpen voorspellingscode in te voegen om de voorwaarde te bevoordelen, rekening houdend met de informatie die door de gebruiker wordt verstrekt. GCC ondersteunt andere ingebouwde onderdelen die het gedrag van het draaiende programma kunnen veranderen of low-level instructies kunnen uitzenden zoals het wissen van de cache, enz. Zie deze documentatie die door de beschikbare ingebouwde GCC's gaat.
Normaal gesproken worden dit soort optimalisaties voornamelijk aangetroffen in hard-real-time applicaties of embedded systemen waar de uitvoeringstijd belangrijk en cruciaal is. Als u bijvoorbeeld een foutconditie zoekt die slechts 1/10000000 keer voorkomt, waarom zou u de compiler daar dan niet over informeren? Op deze manier zou de vertakkingsvoorspelling standaard aannemen dat de voorwaarde onwaar is.
|
Veelgebruikte Booleaanse bewerkingen in C ++ produceren veel branches in het gecompileerde programma. Als deze branches zich binnen loops bevinden en moeilijk te voorspellen zijn, kunnen ze de uitvoering aanzienlijk vertragen. Booleaanse variabelen worden opgeslagen als 8-bits gehele getallen met de waarde 0 voor false en 1 voor true.
Booleaanse variabelen zijn overgedetecteerd in die zin dat alle operatoren die Booleaanse variabelen als invoer hebben, controleren of de invoer een andere waarde heeft dan 0 of 1, maar operators die Booleaanse waarden als uitvoer hebben, kunnen geen andere waarde produceren dan 0 of 1. Dit maakt bewerkingen met Booleaanse variabelen als invoer minder efficiënt dan nodig.
Beschouw een voorbeeld:
bool a, b, c, d;
c = a && b;
d = a || b;
Dit wordt doorgaans op de volgende manier door de compiler geïmplementeerd:
bool a, b, c, d;
if (a! = 0) {
if (b! = 0) {
c = 1;
}
anders {
ga naar CFALSE;
}
}
anders {
CFALSE:
c = 0;
}
if (a == 0) {
if (b == 0) {
d = 0;
}
anders {
ga naar DTRUE;
}
}
anders {
DTRUE:
d = 1;
}
Deze code is verre van optimaal. De takken kunnen lang duren in geval van verkeerde voorspellingen. De Booleaanse bewerkingen kunnen veel efficiënter worden gemaakt als met zekerheid bekend is dat de operanden geen andere waarden hebben dan 0 en 1. De reden waarom de compiler zo'n aanname niet doet, is dat de variabelen andere waarden kunnen hebben als ze niet geïnitialiseerd zijn of afkomstig zijn van onbekende bronnen. De bovenstaande code kan worden geoptimaliseerd als a en b zijn geïnitialiseerd met geldige waarden of als ze afkomstig zijn van operatoren die Booleaanse uitvoer produceren. De geoptimaliseerde code ziet er als volgt uit:
char a = 0, b = 1, c, d;
c = a & b;
d = een | b;
char wordt gebruikt in plaats van bool om het mogelijk te maken om de bitsgewijze operatoren (& en |) te gebruiken in plaats van de Booleaanse operatoren (&& en ||). De bitsgewijze operatoren zijn enkele instructies die slechts één klokcyclus in beslag nemen. De OF-operator (|) werkt zelfs als a en b andere waarden hebben dan 0 of 1. De EN-operator (&) en de EXCLUSIEVE OF-operator (^) kunnen inconsistente resultaten opleveren als de operanden andere waarden hebben dan 0 en 1.
~ kan niet worden gebruikt voor NOT. In plaats daarvan,je kunt een Boolean NOT maken op een variabele waarvan bekend is dat deze 0 of 1 is door deze te XOR'en met 1:
bool a, b;
b =! a;
kan worden geoptimaliseerd om:
char a = 0, b;
b = a ^ 1;
a && b kan niet worden vervangen door a & b als b een uitdrukking is die niet mag worden geëvalueerd als a onwaar is (&& zal b niet evalueren, & zal). Evenzo is een || b kan niet worden vervangen door een | b als b een uitdrukking is die niet moet worden geëvalueerd als a waar is.
Het gebruik van bitsgewijze operatoren is voordeliger als de operanden variabelen zijn dan als de operanden vergelijkingen zijn:
bool a; dubbele x, y, z;
a = x> y && z <5,0;
is in de meeste gevallen optimaal (tenzij u verwacht dat de uitdrukking && veel vertakkingsfouten zal genereren).
|
Dat is zeker!...
Vertakkingsvoorspelling zorgt ervoor dat de logica langzamer werkt, vanwege de omschakeling die plaatsvindt in uw code! Het is alsof je een rechte straat of een straat met veel afslagen gaat, de rechte gaat zeker sneller! ...
Als de array is gesorteerd, is uw voorwaarde onwaar bij de eerste stap: data [c]> = 128, en wordt dan een echte waarde voor de hele weg tot het einde van de straat. Zo kom je sneller tot het einde van de logica. Aan de andere kant, als je een ongesorteerde array gebruikt, heb je veel draaien en verwerken nodig, waardoor je code zeker langzamer werkt ...
Kijk naar de afbeelding die ik hieronder voor je heb gemaakt. Welke straat wordt sneller afgewerkt?
Programmatisch zorgt branchevoorspelling ervoor dat het proces langzamer verloopt ...
Aan het einde is het ook goed om te weten dat we twee soorten vertakkingsvoorspellingen hebben die elk uw code anders zullen beïnvloeden:
1. Statisch
2. Dynamisch
Statische vertakkingsvoorspelling wordt de eerste keer door de microprocessor gebruikt
een voorwaardelijke vertakking wordt aangetroffen, en dynamische vertakkingsvoorspelling is
gebruikt voor opeenvolgende uitvoeringen van de voorwaardelijke filiaalcode.
Om uw code effectief te schrijven om hiervan te profiteren
regels, controleer bij het schrijven van if-else of switch statements de meeste
veelvoorkomende gevallen eerst en werk geleidelijk tot de minst voorkomende.
Voor lussen is niet per se een speciale volgorde van code vereist
statische vertakkingsvoorspelling, als alleen de conditie van de lus-iterator
wordt normaal gebruikt.
|
Deze vraag is al vele malen uitstekend beantwoord. Toch zou ik de aandacht van de groep willen vestigen op nog een andere interessante analyse.
Onlangs werd dit voorbeeld (zeer licht gewijzigd) ook gebruikt als een manier om te demonstreren hoe een stuk code kan worden geprofileerd binnen het programma zelf op Windows. Onderweg laat de auteur ook zien hoe de resultaten kunnen worden gebruikt om te bepalen waar de code de meeste tijd doorbrengt in zowel gesorteerde als ongesorteerde gevallen. Ten slotte laat het stuk ook zien hoe je een weinig bekende functie van de HAL (Hardware Abstraction Layer) kunt gebruiken om te bepalen hoeveel vertakkingsfouten er in het ongesorteerde geval gebeuren.
De link is hier:
Een demonstratie van zelfprofilering
|
Zoals wat al door anderen is genoemd, wat achter het mysterie zit, is Branch Predictor.
Ik probeer niet iets toe te voegen, maar leg het concept op een andere manier uit.
Er is een beknopte introductie op de wiki die tekst en diagram bevat.
Ik hou van de onderstaande uitleg die een diagram gebruikt om de Branch Predictor intuïtief uit te werken.
In computerarchitectuur is een vertakkingsvoorspeller een
digitaal circuit dat probeert te raden in welke richting een vertakking (bijv. een
if-then-else-structuur) gaan voordat dit zeker bekend is. De
doel van de branch voorspeller is om de stroom in de
instructie pijplijn. Branch voorspellers spelen een cruciale rol in
het bereiken van hoge effectieve prestaties in veel moderne pijplijnen
microprocessorarchitecturen zoals x86.
Tweerichtingsvertakking wordt meestal geïmplementeerd met een voorwaardelijke sprong
instructie. Een voorwaardelijke sprong kan ofwel "niet worden gemaakt" en doorgaan
uitvoering met de eerste tak van code die onmiddellijk volgt
na de voorwaardelijke sprong, of het kan worden "genomen" en spring naar een
een andere plaats in het programmageheugen waar de tweede tak van de code is
opgeslagen. Het is niet zeker of er een voorwaardelijke sprong zal zijn
genomen of niet genomen totdat de voorwaarde is berekend en de
voorwaardelijke sprong heeft de uitvoeringsfase in de instructie gepasseerd
pijpleiding (zie afb.1).
Op basis van het beschreven scenario heb ik een animatiedemo geschreven om te laten zien hoe instructies in een pijplijn worden uitgevoerd in verschillende situaties.
Zonder de Branch Predictor.
Zonder vertakkingsvoorspelling zou de processor moeten wachten tot het
voorwaardelijke spronginstructie heeft de uitvoeringsfase gepasseerd voordat de
volgende instructie kan de ophaalfase in de pijplijn ingaan.
Het voorbeeld bevat drie instructies en de eerste is een voorwaardelijke spronginstructie. De laatste twee instructies kunnen de pijplijn ingaan totdat de voorwaardelijke spronginstructie is uitgevoerd.
Het duurt 9 klokcycli voordat 3 instructies zijn voltooid.
Gebruik Branch Predictor en maak geen voorwaardelijke sprong. Laten we aannemen dat de voorspelling niet devoorwaardelijke sprong.
Het duurt 7 klokcycli voordat 3 instructies zijn voltooid.
Gebruik Branch Predictor en maak een voorwaardelijke sprong. Laten we aannemen dat de voorspelling niet de voorwaardelijke sprong maakt.
Het duurt 9 klokcycli voordat 3 instructies zijn voltooid.
De tijd die wordt verspild in het geval van een verkeerde voorspelling van een filiaal is gelijk aan
het aantal fasen in de pijplijn vanaf de ophaalfase tot het
etappe uitvoeren. Moderne microprocessors hebben de neiging om vrij lang te duren
pijpleidingen zodat de vertraging van de verkeerde voorspelling tussen 10 en 20 uur ligt
cycli. Als gevolg hiervan vergroot het verlengen van een pijpleiding de behoefte aan een
meer geavanceerde branch voorspeller.
Zoals u kunt zien, lijkt het erop dat we geen reden hebben om Branch Predictor niet te gebruiken.
Het is een vrij eenvoudige demo die het basisgedeelte van Branch Predictor verduidelijkt. Als die gifs vervelend zijn, verwijder ze dan gerust uit het antwoord en bezoekers kunnen ook de live demo-broncode krijgen van BranchPredictorDemo
|
Winst voor branchevoorspelling!
Het is belangrijk om te begrijpen dat een verkeerde voorspelling van branches de programma's niet vertraagt. De kosten van een gemiste voorspelling zijn net alsof er geen vertakkingsvoorspelling bestond en je wachtte op de evaluatie van de uitdrukking om te beslissen welke code er moest worden uitgevoerd (verdere uitleg in de volgende paragraaf).
if (uitdrukking)
{
// Voer 1 uit
} anders {
// Voer 2 uit
}
Elke keer dat er een if-else \ switch-instructie is, moet de expressie worden geëvalueerd om te bepalen welk blok moet worden uitgevoerd. In de assembly-code die door de compiler wordt gegenereerd, worden voorwaardelijke vertakkingsinstructies ingevoegd.
Een vertakte instructie kan ervoor zorgen dat een computer begint met het uitvoeren van een andere instructiesequentie en dus afwijkt van het standaardgedrag van het uitvoeren van instructies in volgorde (dwz als de uitdrukking onwaar is, slaat het programma de code van het if-blok over), afhankelijk van een bepaalde voorwaarde, is de uitdrukking evaluatie in ons geval.
Dat gezegd hebbende, probeert de compiler de uitkomst te voorspellen voordat deze daadwerkelijk wordt geëvalueerd. Het haalt instructies op uit het if-blok, en als de uitdrukking waar blijkt te zijn, dan geweldig! We hebben de tijd gewonnen die nodig was om het te evalueren en boekten vooruitgang in de code; zo niet, dan voeren we de verkeerde code uit, wordt de pijplijn doorgespoeld en wordt het juiste blok uitgevoerd.
Visualisatie:
Stel dat u route 1 of route 2 moet kiezen. Wachtend op uw partner om de kaart te bekijken, u bent gestopt bij ## en gewacht, of u kunt gewoon route 1 kiezen en als u geluk heeft (route 1 is de juiste route), geweldig, je hoefde niet te wachten tot je partner de kaart had gecontroleerd (je hebt de tijd bespaard die hij nodig zou hebben gehad om de kaart te controleren), anders keer je gewoon terug.
Hoewel het doorspoelen van pijpleidingen supersnel gaat, is het tegenwoordig de moeite waard om deze gok te wagen. Het voorspellen van gesorteerde gegevens of gegevens die langzaam veranderen, is altijd gemakkelijker en beter dan het voorspellen van snelle veranderingen.
O Route 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Route 2 \ --------------------------------
|
Op ARM is er geen aftakking nodig, omdat elke instructie een 4-bits conditieveld heeft, dat (zonder kosten) 16 verschillende condities test die kunnen optreden in het Processor Status Register, en of de conditie van een instructie is false, de instructie wordt overgeslagen. Dit elimineert de noodzaak voor korte vertakkingen, en er zou geen voorspelling van de vertakkingen zijn voor dit algoritme. Daarom zou de gesorteerde versie van dit algoritme langzamer werken dan de ongesorteerde versie op ARM, vanwege de extra overhead van sorteren.
De binnenste lus voor dit algoritme zou er ongeveer als volgt uitzien in de ARM-assembleertaal:
MOV R0, # 0 // R0 = som = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, data // R2 = addr van datamatrix (plaats deze instructie buiten de buitenste lus)
.inner_loop // Label met aftakking binnenste lus
LDRB R3, [R2, R1] // R3 = gegevens [c]
CMP R3, # 128 // vergelijk R3 met 128
TOEVOEGEN R0, R0, R3 // als R3> = 128, dan som + = data [c] - geen vertakking nodig!
VOEG R1, R1, # 1 // c ++ toe
CMP R1, #arraySize // vergelijk c met arraySize
BLT inner_loop // Vertakking naar inner_loop als c  ());
voor (unsigned c = 0; c  = 128
som = som + data1 (j);
einde
einde
einde
toc;
ExeTimeWithSorting = toc - tic;
De resultaten voor de bovenstaande MATLAB-code zijn als volgt:
a: Verstreken tijd (zonder sortering) = 3479.880861 seconden.
b: Verstreken tijd (met sortering) = 2377,873098 seconden.
De resultaten van de C-code zoals in @GManNickG krijg ik:
a: Verstreken tijd (zonder sortering) = 19,8761 sec.
b: Verstreken tijd (met sortering) = 7,37778 sec.
Op basis hiervan lijkt het erop dat MATLAB bijna 175 keer langzamer is dan de C-implementatie zonder sorteren en 350 keer langzamer met sorteren. Met andere woorden, het effect (van vertakkingsvoorspelling) is 1,46x voor MATLAB-implementatie en 2,7x voor de C-implementatie.
|
De veronderstelling van andere antwoorden dat men de gegevens moet sorteren, is niet correct.
De volgende code sorteert niet de hele array, maar slechts 200-elementsegmenten ervan, en werkt daardoor het snelst.
Door alleen k-elementsecties te sorteren, wordt de voorverwerking voltooid in lineaire tijd, O (n), in plaats van de O (n.log (n)) tijd die nodig is om de hele array te sorteren.
# include 
# include 
# include 
int main () {
int gegevens [32768]; const int l = grootte van gegevens / grootte van gegevens [0];
voor (unsigned c = 0; c  = 128)
som + = data [c];
}
}
std :: cout << static_cast  (clock () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << som << std :: endl;
}
Dit "bewijst" ook dat het niets te maken heeft met een algoritmisch probleem zoals de sorteervolgorde, en het is inderdaad vertakkingsvoorspelling.
|
Bjarne Stroustrup's antwoord op deze vraag:
Dat klinkt als een interviewvraag. Is het waar? Hoe zou u dat weten? Het is een slecht idee om vragen over efficiëntie te beantwoorden zonder eerst wat metingen te doen, dus het is belangrijk om te weten hoe je moet meten.
Dus ik probeerde met een vector van een miljoen gehele getallen en kreeg:
Al 32995 milliseconden gesorteerd
Geschud 125944 milliseconden
Al 18610 milliseconden gesorteerd
Geschud 133304 milliseconden
Al 17942 milliseconden gesorteerd
Geschudde 107858 milliseconden
Ik heb dat een paar keer gedaan om zeker te zijn. Ja, het fenomeen is echt. Mijn sleutelcode was:
void run (vector  & v, const string & label)
{
auto t0 = system_clock :: now ();
sorteren (v.begin (), v.end ());
auto t1 = system_clock :: now ();
cout << label
<< duration_cast  (t1 - t0) .count ()
<< "milliseconden \ n";
}
leegte tst ()
{
vector  v (1'000'000);
iota (v.begin (), v.end (), 0);
run (v, "al gesorteerd");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
run (v, "shuffled");
}
Het fenomeen is tenminste reëel met deze compiler, standaardbibliotheek en optimalisatie-instellingen. Verschillende implementaties kunnen en zullen verschillende antwoorden geven. In feite heeft iemand een meer systematisch onderzoek gedaan (een snelle zoekopdracht op internet zal het vinden) en de meeste implementaties laten dat effect zien.
Een reden is vertakkingsvoorspelling: de sleutelbewerking in het sorteeralgoritme is "if (v [i]  = 128. Dat betekent dat we gemakkelijk een enkele bit kunnen extraheren die ons vertelt of we een waarde willen of niet: door te verschuiven de data aan de rechterkant 7 bits, we houden een 0 bit of een 1 bit over, en we willen de waarde alleen optellen als we een 1 bit hebben. Laten we dit bit het "beslissingsbit" noemen.
Door de 0/1 waarde van de beslissingsbit te gebruiken als een index in een array, kunnen we code maken die even snel is, of de gegevens nu gesorteerd of niet gesorteerd zijn. Onze code voegt altijd een waarde toe, maar als de beslissingsbit 0 is, voegen we de waarde ergens toe waar we niet om geven. Hier is de code:
// Test
clock_t start = klok ();
lang lang a [] = {0, 0};
lange lange som;
voor (unsigned i = 0; i <100000; ++ i)
{
// Primaire lus
voor (unsigned c = 0; c > 7);
a [j] + = data [c];
}
}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
som = a [1];
Deze code verspilt de helft van de toevoegingen, maar heeft nooit een vertakkingsfout. Het is enorm sneller op willekeurige gegevens dan de versie met een feitelijke if-instructie.
Maar bij mijn testen was een expliciete opzoektabel iets sneller dan dit, waarschijnlijk omdat het indexeren in een opzoektabel iets sneller ging dan het verschuiven van bits. Dit laat zien hoe mijn code de opzoektabel instelt en gebruikt (onvoorstelbaar lut genoemd voor "LookUp Table" in de code). Hier is de C ++ -code:
// Declareer en vul de opzoektabel in
int lut [256];
voor (unsigned c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Gebruik de opzoektabel nadat deze is gebouwd
voor (unsigned i = 0; i <100000; ++ i)
{
// Primaire lus
voor (unsigned c = 0; c  waarde)
knooppunt = knooppunt-> pLeft;
anders
knooppunt = knooppunt-> pRight;
deze bibliotheek zou zoiets doen als:
i = (x  waarde);
knooppunt = knooppunt-> link [i];
Het is een mooie oplossing en misschien zal het werken.
|
Zeer actieve vraag. Verdien 10 reputatie om deze vraag te beantwoorden. De reputatievereiste helpt deze vraag te beschermen tegen spam en niet-beantwoording.
Niet het antwoord waar je naar zoekt? Blader door andere vragen met de tag java c ++ performance optimization branch-voorspelling of stel uw eigen vraag.